{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Line Reflection"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isReflected"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #直线镜像"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在一个二维平面空间中，给你 n&nbsp;个点的坐标。问，是否能找出一条平行于 y<strong>&nbsp;</strong>轴的直线，让这些点关于这条直线成镜像排布？</p>\n",
    "\n",
    "<p><strong>注意</strong>：题目数据中可能有重复的点。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/04/23/356_example_1.PNG\" style=\"width: 389px; height: 340px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>points = [[1,1],[-1,1]]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>可以找出 x = 0 这条线。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/04/23/356_example_2.PNG\" style=\"width: 300px; height: 294px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>points = [[1,1],[-1,-1]]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>无法找出这样一条线。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == points.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10^4</code></li>\n",
    "\t<li><code>-10^8&nbsp;&lt;= points[i][j] &lt;=&nbsp;10^8</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>你能找到比 O(<em>n</em><sup>2</sup>) 更优的解法吗?</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [line-reflection](https://leetcode.cn/problems/line-reflection/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [line-reflection](https://leetcode.cn/problems/line-reflection/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,1],[-1,1]]', '[[1,1],[-1,-1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReflected(self, points: List[List[int]]) -> bool:\n",
    "        points.sort(key=lambda x: x[0])\n",
    "        min_x = points[0][0]\n",
    "        max_x = points[-1][0]\n",
    "        mid_x = (min_x + max_x) / 2\n",
    "        \n",
    "        for _x, _y in points:\n",
    "            new_x = 2 * mid_x - _x\n",
    "            if [new_x, _y] not in points:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReflected(self, points: List[List[int]]) -> bool:\n",
    "        points.sort(key=lambda x: x[0])\n",
    "        min_x = points[0][0]\n",
    "        max_x = points[-1][0]\n",
    "        mid_x = (min_x + max_x) / 2\n",
    "        \n",
    "        for _x, _y in points:\n",
    "            new_x = 2 * mid_x - _x\n",
    "            if [new_x, _y] not in points:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReflected(self, points: List[List[int]]) -> bool:\n",
    "        points.sort(key=lambda x: x[0])\n",
    "        min_x = points[0][0]\n",
    "        max_x = points[-1][0]\n",
    "        mid_x = (min_x + max_x) / 2\n",
    "        \n",
    "        for _x, _y in points:\n",
    "            new_x = 2 * mid_x - _x\n",
    "            if [new_x, _y] not in points:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReflected(self, points: List[List[int]]) -> bool:\n",
    "        y_to_x = {}\n",
    "        for x, y in points:\n",
    "            if y not in y_to_x:\n",
    "                y_to_x[y] = set()\n",
    "            y_to_x[y].add(x)\n",
    "        \n",
    "        val_lst = list(y_to_x[points[0][1]])\n",
    "        val_lst.sort()\n",
    "        target_mid = (val_lst[0] + val_lst[-1]) / 2\n",
    "        for val_set in y_to_x.values():\n",
    "            val_lst = list(val_set)\n",
    "            val_lst.sort()\n",
    "            left, right = 0, len(val_lst) - 1\n",
    "            while left <= right:\n",
    "                temp_mid = (val_lst[left] + val_lst[right]) / 2\n",
    "                if temp_mid != target_mid:\n",
    "                    return False\n",
    "                left += 1\n",
    "                right -= 1\n",
    "        \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReflected(self, points: List[List[int]]) -> bool:\n",
    "        m = defaultdict(list)\n",
    "        points.sort()\n",
    "        for x, y in points:\n",
    "            cur = m[y]\n",
    "            if (not cur) or cur[-1] != x:\n",
    "                cur.append(x)\n",
    "\n",
    "        def check(m):\n",
    "            l, r = 0, len(m) - 1\n",
    "            tar = m[0] + m[-1] if len(m) % 2 == 0 else m[len(m) // 2] * 2\n",
    "            while l < r:\n",
    "                if m[0] + m[-1] != tar:\n",
    "                    return False, None\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            return True, tar\n",
    "        cur = None\n",
    "        # 每个点的集合都进行一次check y值相同 看看分界线x是不是一样的\n",
    "        # 复杂度 就是\n",
    "        for y in m:\n",
    "            can, line = check(m[y])\n",
    "            if not can:\n",
    "                return False\n",
    "            if cur is None:\n",
    "                cur = line\n",
    "            elif cur != line:\n",
    "                return False\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReflected(self, points: List[List[int]]) -> bool:\n",
    "        n = len(points)\n",
    "        if n == 1:\n",
    "            return True\n",
    "        dic = {}\n",
    "        for pt in points:\n",
    "            if pt[1] in dic:\n",
    "                if pt[0] not in dic[pt[1]]:\n",
    "                    dic[pt[1]].append(pt[0])\n",
    "            else:\n",
    "                dic[pt[1]] = [pt[0]]\n",
    "        visited = set()\n",
    "        for k, v in dic.items():\n",
    "            m = len(v)\n",
    "            mid = sum(v)/m\n",
    "            if visited:\n",
    "                if mid not in visited:\n",
    "                    return False\n",
    "            else:\n",
    "                visited.add(mid)\n",
    "            while v:\n",
    "                tmp = v.pop()\n",
    "                if tmp == mid:\n",
    "                    continue\n",
    "                tmp = mid*2 - tmp \n",
    "                if tmp in v:\n",
    "                    v.remove(tmp)\n",
    "                else:\n",
    "                    return False\n",
    "\n",
    "        return True      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReflected(self, points: List[List[int]]) -> bool:\n",
    "        points.sort(key=lambda x: x[0])\n",
    "        min_x = points[0][0]\n",
    "        max_x = points[-1][0]\n",
    "        mid_x = (min_x + max_x) / 2\n",
    "        \n",
    "        seen = set()\n",
    "        for _x, _y in points:\n",
    "            if (_x, _y) in seen:\n",
    "                continue\n",
    "            # 关于跟Y轴平行的线对称，获取镜像点的坐标\n",
    "            new_x = 2 * mid_x - _x\n",
    "            if [new_x, _y] not in points:\n",
    "                return False\n",
    "            seen.add((_x, _y))\n",
    "            seen.add((new_x, _y))\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReflected(self, points: List[List[int]]) -> bool:\n",
    "        points.sort()\n",
    "        if len(points) == 1:\n",
    "            return True\n",
    "        x = (points[0][0] + points[len(points) - 1][0]) / 2\n",
    "        left, right = set(), set()\n",
    "\n",
    "        for point in points:\n",
    "            if point[0] < x:\n",
    "                left.add((point[0], point[1]))\n",
    "            elif point[0] > x:\n",
    "                right.add((point[0], point[1]))\n",
    "\n",
    "        if len(left) != len(right):\n",
    "            return False\n",
    "        for o in left:\n",
    "            i, j = 2 * x - o[0], o[1]\n",
    "            if (i, j) not in right:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReflected(self, points: List[List[int]]) -> bool:\n",
    "        m = defaultdict(set)\n",
    "        for x, y in points:\n",
    "            m[y].add(x)\n",
    "\n",
    "        def check(m):\n",
    "            m = list(sorted(m))\n",
    "            l, r = 0, len(m) - 1\n",
    "            tar = m[0] + m[-1] if len(m) % 2 == 0 else m[len(m) // 2] * 2\n",
    "            while l < r:\n",
    "                if m[0] + m[-1] != tar:\n",
    "                    return False, None\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            return True, tar\n",
    "        cur = None\n",
    "        for y in m:\n",
    "            can, line = check(m[y])\n",
    "            if not can:\n",
    "                return False\n",
    "            if cur is None:\n",
    "                cur = line\n",
    "            elif cur != line:\n",
    "                return False\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReflected(self, points: List[List[int]]) -> bool:\n",
    "        if not points:\n",
    "            return True\n",
    "\n",
    "        points.sort(key=lambda x:(x[0],x[1]))\n",
    "        sum=points[0][0]+points[-1][0]\n",
    "        seen={}\n",
    "\n",
    "        for x,y in points: \n",
    "            if [sum-x,y] not in points:\n",
    "                return False\n",
    "        return True\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReflected(self, points: List[List[int]]) -> bool:\n",
    "        mp = defaultdict(set)\n",
    "        for x, y in points:\n",
    "            mp[y].add(x)\n",
    "        # print(f'{mp}')\n",
    "        ## check each y\n",
    "        axis = -1\n",
    "        for k, v in mp.items():\n",
    "            a = sorted(list(v))\n",
    "            c = (a[-1] + a[0]) / 2\n",
    "            # print(f'{a, c}')\n",
    "            if axis != -1 and abs(c - axis) > 0.0001:\n",
    "                return False\n",
    "            l, r = 1, len(a) - 2\n",
    "            while l <= r:\n",
    "                diff = abs((a[l] + a[r])/ 2 - c)\n",
    "                # print(f'{diff}')\n",
    "                if diff > 0.0001:\n",
    "                    return False\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            if axis == -1:\n",
    "                axis = c\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReflected(self, points: List[List[int]]) -> bool:\n",
    "        d = {}\n",
    "        for x, y in points:\n",
    "            if y not in d:\n",
    "                d[y] = {x}\n",
    "            else:\n",
    "                d[y].add(x)\n",
    "        s = None\n",
    "        for v in d.values():\n",
    "            v = list(v)\n",
    "            v.sort()\n",
    "            x = v[0] + v[-1]\n",
    "            i, j = 1, len(v) - 2\n",
    "            while i <= j:\n",
    "                if v[i] + v[j] != x:\n",
    "                    return False\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            if s is None:\n",
    "                s = x\n",
    "            elif s != x:\n",
    "                return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReflected(self, points: List[List[int]]) -> bool:\n",
    "        dic={}\n",
    "        for p in points:\n",
    "            if p[1] in dic.keys() and p[0] not in dic[p[1]]:\n",
    "                dic[p[1]].append(p[0])\n",
    "            else:\n",
    "                dic[p[1]]=[p[0]]\n",
    "        base=10**9\n",
    "        for j in dic.keys():\n",
    "            l=sorted(dic[j])\n",
    "            ll=len(l)\n",
    "            print(ll)\n",
    "            if base>10**8:\n",
    "                base=(l[0]+l[-1])/2\n",
    "            for t in range(ll):\n",
    "                if l[t]+l[ll-1-t]!=base*2:\n",
    "                    return False \n",
    "        return True\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReflected(self, points: List[List[int]]) -> bool:\n",
    "        \n",
    "        # find line x = a\n",
    "\n",
    "\n",
    "        st = set()\n",
    "        for px, py in points:\n",
    "            st.add((px, py))\n",
    "\n",
    "        sx = 0\n",
    "        n = len(st)\n",
    "        for x, y in st:\n",
    "            sx += x\n",
    "        a = sx / n\n",
    "\n",
    "\n",
    "        for px, py in st:\n",
    "            if px == a:\n",
    "                # 在对称轴上，没有对应的点\n",
    "                continue\n",
    "            elif (2 * a - px, py) in st:\n",
    "                continue\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        return True\n",
    "            \n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReflected(self, points: List[List[int]]) -> bool:\n",
    "        min_x = float('inf')\n",
    "        max_x = float('-inf')\n",
    "        seen = set()\n",
    "        for x, y in points:\n",
    "            min_x = min(min_x, x)\n",
    "            max_x = max(max_x, x)\n",
    "            seen.add((x,y))\n",
    "        m = (max_x+min_x)/2\n",
    "        for ele in seen:\n",
    "            x,y = ele\n",
    "            if ((m-x+m),y) not in seen:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReflected(self, points: List[List[int]]) -> bool:\n",
    "        # 先找到中间的x，即为要找到的直线，再查看相同y下是否有点与它对称\n",
    "        l = float('inf')\n",
    "        r = -float('inf')\n",
    "        seen = set()\n",
    "        for x, y in points:\n",
    "            l = min(l, x)\n",
    "            r = max(r, x)\n",
    "            seen.add((x, y))\n",
    "        m = (l + r) / 2\n",
    "        for ele in seen:\n",
    "            x, y = ele\n",
    "            if ((2 * m - x), y) not in seen:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReflected(self, points: List[List[int]]) -> bool:\n",
    "        points=[tuple(points[i]) for i in range(len(points))]\n",
    "        points=set(points)\n",
    "        num=len(points)\n",
    "        cnt=Counter(points)\n",
    "        sum_x=0\n",
    "        for key,val in cnt.items():\n",
    "            sum_x+=key[0]*val\n",
    "        x=sum_x/num\n",
    "        print(sum_x)\n",
    "        for key,val in cnt.items():\n",
    "            if (2*x-key[0],key[1]) in cnt:\n",
    "                pass\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReflected(self, points: List[List[int]]) -> bool:\n",
    "        # 先找到中间的x，即为要找到的直线，再查看相同y下是否有点与它对称\n",
    "        l = float('inf')\n",
    "        r = -float('inf')\n",
    "        seen = set()\n",
    "        for x, y in points:\n",
    "            l = min(l, x)\n",
    "            r = max(r, x)\n",
    "            seen.add((x, y))\n",
    "        m = (l + r) / 2\n",
    "        for ele in seen:\n",
    "            x, y = ele\n",
    "            if ((2 * m - x), y) not in seen:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReflected(self, points: List[List[int]]) -> bool:\n",
    "        # 先找到中间的x，即为要找到的直线，再查看相同y下是否有点与它对称\n",
    "        l = float('inf')\n",
    "        r = -float('inf')\n",
    "        seen = set()\n",
    "        for x, y in points:\n",
    "            l = min(l, x)\n",
    "            r = max(r, x)\n",
    "            seen.add((x, y))\n",
    "        m = (l + r) / 2\n",
    "        for ele in seen:\n",
    "            x, y = ele\n",
    "            if ((2 * m - x), y) not in seen:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReflected(self, points: List[List[int]]) -> bool:\n",
    "        points=list(set(map(tuple,points)))\n",
    "        dic={}\n",
    "        points.sort()\n",
    "        for i in points:\n",
    "            x,y=i[0],i[1]\n",
    "            if y not in dic:\n",
    "                dic[y]=[x]\n",
    "            else:\n",
    "                dic[y].append(x)\n",
    "        def check(lst):\n",
    "            if len(lst)%2==1:\n",
    "                mid=lst[len(lst)//2]\n",
    "                for i in range(len(lst)):\n",
    "                    if lst[i]+lst[len(lst)-1-i]!=mid*2:\n",
    "                        return 'F'\n",
    "                return mid\n",
    "            else:\n",
    "                csum=lst[0]+lst[-1]\n",
    "                for i in range(len(lst)):\n",
    "                    if lst[i]+lst[len(lst)-1-i]!=csum:\n",
    "                        return 'F'\n",
    "                return csum/2\n",
    "\n",
    "       \n",
    "        t=None\n",
    "        for i in dic:\n",
    "            if not t:\n",
    "                t=check(dic[i])\n",
    "                if t!='F':\n",
    "                    now=t\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                g=check(dic[i])\n",
    "                if g=='F' or g!=t:\n",
    "                    return False\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReflected(self, points: List[List[int]]) -> bool:\n",
    "        # 先找到中间的x，即为要找到的直线，再查看相同y下是否有点与它对称\n",
    "        l = float('inf')\n",
    "        r = -float('inf')\n",
    "        seen = set()\n",
    "        for x, y in points:\n",
    "            l = min(l, x)\n",
    "            r = max(r, x)\n",
    "            seen.add((x, y))\n",
    "        m = (l + r) / 2\n",
    "        for ele in seen:\n",
    "            x, y = ele\n",
    "            if ((2 * m - x), y) not in seen:\n",
    "                return False\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReflected(self, points: List[List[int]]) -> bool:\n",
    "        points=list(set([(x,y) for x,y in points]))\n",
    "        n=len(points)\n",
    "        maxx=max(points[i][0] for i in range(n))\n",
    "        minx=min(points[i][0] for i in range(n))\n",
    "        zhou=(maxx+minx)/2\n",
    "        while len(points)>0:\n",
    "            p=points.pop(0)\n",
    "            if p[0]==zhou: continue\n",
    "            try: points.remove((2*zhou-p[0],p[1]))\n",
    "            except ValueError:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReflected(self, points: List[List[int]]) -> bool:\n",
    "        mp = defaultdict(set)\n",
    "        for x, y in points:\n",
    "            mp[y].add(x)\n",
    "        print(f'{mp}')\n",
    "        ## check each y\n",
    "        axis = -1\n",
    "        for k, v in mp.items():\n",
    "            a = sorted(list(v))\n",
    "            c = (a[-1] + a[0]) / 2\n",
    "            # print(f'{a, c}')\n",
    "            if axis != -1 and abs(c - axis) > 0.0001:\n",
    "                return False\n",
    "            l, r = 1, len(a) - 2\n",
    "            while l <= r:\n",
    "                diff = abs((a[l] + a[r])/ 2 - c)\n",
    "                # print(f'{diff}')\n",
    "                if diff > 0.0001:\n",
    "                    return False\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            if axis == -1:\n",
    "                axis = c\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReflected(self, points: List[List[int]]) -> bool:\n",
    "        mp = defaultdict(set)\n",
    "        for x, y in points:\n",
    "            mp[y].add(x)\n",
    "        print(f'{mp}')\n",
    "        ## check each y\n",
    "        axis = -1\n",
    "        for k, v in mp.items():\n",
    "            a = sorted(list(v))\n",
    "            c = (a[-1] + a[0]) / 2\n",
    "            # print(f'{a, c}')\n",
    "            if axis != -1 and abs(c - axis) > 0.0001:\n",
    "                return False\n",
    "            l, r = 1, len(a) - 2\n",
    "            while l <= r:\n",
    "                diff = abs((a[l] + a[r])/ 2 - c)\n",
    "                # print(f'{diff}')\n",
    "                if diff > 0.0001:\n",
    "                    return False\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            if axis == -1:\n",
    "                axis = c\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReflected(self, points: List[List[int]]) -> bool:\n",
    "        mid = min(points)[0] + max(points)[0]\n",
    "        vis = {}\n",
    "        vis = {(x, y) for x, y in points}\n",
    "        for x, y in vis:\n",
    "            if (mid - x, y) not in vis:\n",
    "                return False\n",
    "        return True\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReflected(self, points: List[List[int]]) -> bool:\n",
    "        \n",
    "        # find line x = a\n",
    "\n",
    "\n",
    "        st = set()\n",
    "        for px, py in points:\n",
    "            st.add((px, py))\n",
    "\n",
    "        sx = 0\n",
    "        n = len(st)\n",
    "        for x, y in st:\n",
    "            sx += x\n",
    "        a = sx / n\n",
    "\n",
    "\n",
    "        for px, py in st:\n",
    "            if px == a:\n",
    "                # 在对称轴上，没有对应的点\n",
    "                continue\n",
    "            elif (2 * a - px, py) in st:\n",
    "                continue\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        return True\n",
    "            \n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReflected(self, points: List[List[int]]) -> bool:\n",
    "        min_x, max_x = inf, -inf\n",
    "        point_set = set()\n",
    "        for x, y in points:\n",
    "            min_x = min(min_x, x)\n",
    "            max_x = max(max_x, x)\n",
    "            point_set.add((x, y))\n",
    "        s = min_x + max_x\n",
    "        return all((s - x, y) in point_set for x, y in points)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReflected(self, points: List[List[int]]) -> bool:\n",
    "        l, r = inf, -inf\n",
    "        seen = set()\n",
    "        for x, y in points:\n",
    "            l = min(l, x)\n",
    "            r = max(r, x)\n",
    "            seen.add((x,y))\n",
    "        m = (l + r) / 2\n",
    "        for x, y in seen:\n",
    "            if (2 * m - x, y) not in seen:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReflected(self, points: List[List[int]]) -> bool:\n",
    "        n = len(points)\n",
    "        cnt = defaultdict(int)\n",
    "        min_x,max_x = inf,-inf\n",
    "        points = [(2*x,y) for x,y in points]\n",
    "        _set = set(points)\n",
    "        points = list(_set)\n",
    "        for x,y in points:\n",
    "            min_x = min(min_x,x)\n",
    "            max_x = max(max_x,x)\n",
    "        ans = (max_x + min_x) // 2\n",
    "        # print(_set,ans)\n",
    "        for x,y in points:\n",
    "            if x <= ans:\n",
    "                if (ans + ans - x,y) not in _set:\n",
    "                    return False\n",
    "                _set.remove((ans + ans - x,y))\n",
    "                if (x,y) in _set:\n",
    "                    _set.remove((x,y))\n",
    "            \n",
    "        return len(_set) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque, defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isReflected(self, points: List[List[int]]) -> bool:\n",
    "        \"\"\"\n",
    "\n",
    "        :param points:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        s1 = set()\n",
    "        for i in points:\n",
    "            s1.add(tuple(i))\n",
    "        points = list(s1)\n",
    "        m1 = defaultdict(list)\n",
    "        for i in points:\n",
    "            m1[i[1]].append(i[0])\n",
    "\n",
    "        mid = None\n",
    "        for k, v in m1.items():\n",
    "            v.sort()\n",
    "            v = deque(v)\n",
    "\n",
    "            while len(v) > 1:\n",
    "                if v[0] + v[-1] != v[1] + v[-2]:\n",
    "                    return False\n",
    "                if mid is None:\n",
    "                    mid = (v[-1] + v[0]) / 2\n",
    "                else:\n",
    "                    if mid != (v[-1] + v[0]) / 2:\n",
    "                        return False\n",
    "                v.popleft()\n",
    "                v.pop()\n",
    "            if len(v) == 1:\n",
    "                if mid is None:\n",
    "                    mid = v[0]\n",
    "                else:\n",
    "                    if mid != v[0]:\n",
    "                        return False\n",
    "\n",
    "        return True\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.isReflected([[1, 1], [9, 1], [8,2]]))\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
